// 31. 下一个排列
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */

/*  
    1.首先，从后向前查找第一个顺序对(i,i+1) 满足 a[i] < a[i+1] 这样[较小的数]即为a[i] 此时(i+1,n)必然是下降序列对
    2.如果找到了顺序对,那么在区间[i+1,n) 中从后向前查找第一个元素j 满足a[i]<a[j] 这样[较大数] 即为a[j]
    3.交换a[i]与a[j],此时可以证明区间[i+1,n)必为降序 我们可以直接使用双指针反转区间[i+1,n)使其变成升序，而无需对该区间进行
        排序

*/
var nextPermutation = function (nums) {
	let i = nums.length - 2
	/* 寻找非降序的a[i-1] */
	while (i >= 0 && nums[i] >= nums[i + 1]) {
		i--
	}
	if (i >= 0) {
		let j = nums.length - 1
		while (j >= 0 && nums[i] >= nums[j]) {
			j--
		}
		swap(nums, i, j)
	}

	reverse(nums, i + 1)
}

const swap = (nums, i, j) => {
	const temp = nums[i]
	nums[i] = nums[j]
	nums[j] = temp
}

const reverse = (nums, start) => {
	let left = start,
		right = nums.length - 1

	while (left < right) {
		swap(nums, left, right)
		left++
		right--
	}
}
nextPermutation([1, 2, 3])
